package demo.practice.dp;

public class P64 {
    public static void main(String[] args) {
        P64 p64 = new P64();
        p64.minPathSum(new int[][]{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}});
    }

    public int minPathSum(int[][] grid) {

        if (grid == null || grid.length == 0 || grid[0].length == 0)
            return 0;
        int h = grid.length, w = grid[0].length;
        int dp[][] = new int[h][w];

        dp[0][0] = grid[0][0];

        // 只能是从上方 或者是左边，转移方程式为
        //  dp[i][j]= min( dp[i-1][j]+ dp[i][j],dp[i][j-1]+ dp[i][j])
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (i > 0 && j > 0) {
                    dp[i][j] = Math.min(dp[i - 1][j] + grid[i][j], dp[i][j - 1] + grid[i][j]);
                } else if (i == 0 && j > 0) {
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                } else if (j == 0 && i > 0) {
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
                }
            }
        }

        return dp[h - 1][w - 1];
    }
}
